80. 删除有序数组中的重复项 II

Similar Question

leading to the advanced question

Solution Tips

方案一: 双指针

仅仅是扩展了跳过的逻辑

var removeDuplicates = function(nums, k) {
    // 只是快速指针跳过的逻辑不同而已, 跳过的元素就相当于是删除
    let slow = 0;
    let fast = 0;
    let count = 0;
    while (fast < nums.length) {
        if (nums[fast] === nums[fast - 1]) {
            if (count < 2) {
                nums[slow] = nums[fast];
                slow++;
                count++
            }
        }
        else {
            // 新元素
            nums[slow] = nums[fast];
            slow++;
            count = 1;
        }
        fast++;
    }

    return slow;

};

方案二: 针对方法一的一些优化

由于是保留 k 个相同数字，对于前 k 个数字，我们可以直接保留。

对于后面的任意数字，能够保留的前提是：与当前写入的位置前面的第 k 个元素进行比较，不相同则保留。

因为是非降序的数组, 所以对于 i < j 且, nums[i] === nums[j], 一定有 i < k < j, 满足 nums[i] = nums[k] = nums[j]

var removeDuplicates = function(nums, k = 2) {
    // 只是快速指针跳过的逻辑不同而已, 跳过的元素就相当于是删除
    // 前 k 个直接保留
    let slow = k;
    let fast = k;
    while (fast < nums.length) {
        if (nums[fast] !== nums[slow - k]) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }

    return slow;

};